package com.linyaonan.leetcode.easy._653;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: Lin
 * @date: 2020/1/4
 */
public class TwoSumIV {
    List<Integer> nodeList = new ArrayList<>();

    public boolean findTarget(TreeNode root, int k) {
        bfs(root);
        int startIndex = 0;
        int endIndex = nodeList.size() - 1;
        while (startIndex < endIndex) {
            int sum = nodeList.get(startIndex) + nodeList.get(endIndex);
            if (sum == k) {
                return true;
            } else {
                if (sum > k) {
                    endIndex--;
                } else {
                    startIndex++;
                }
            }
        }
        return false;
    }

    private void bfs(TreeNode node) {
        if (node != null) {
            bfs(node.left);
            nodeList.add(node.val);
            bfs(node.right);
        }
    }
}
